Video information requires a large amount of storage space, therefore video information is generally compressed before it is stored. Accordingly, to display compressed video information which is stored, for example, on a compact disk read only memory (CD ROM), the compressed video information is decompressed to furnish decompressed video information. The decompressed video information is then communicated in a bit stream to a display. The bit stream of video information is generally stored in a plurality of memory storage locations corresponding to pixel locations on a display. The stored video information is generally referred to as a bit map. The video information representing a single screen of information on a display is called a picture. A goal of many video systems is to quickly and efficiently decode compressed video information to enable a motion video capability.
Standardization of recording media, devices and various aspects of data handling, such as video compression, is highly desirable for continued growth of this technology and its applications. One compression standard which has attained wide spread use for compressing and decompressing video information is the moving pictures expert group (MPEG) standard for video encoding and decoding. The MPEG standard is defined in International Standard ISO/IEC 11172-1, "Information Technology--Coding of moving pictures and associated audio for digital storage media at up to about 1.5 Mbit/s", Parts 1, 2 and 3, First edition 1993-08-01 which is hereby incorporated by reference in its entirety.
Pictures within the MPEG standard are divided into 16.times.16 pixel macroblocks. Each macroblock includes six 8.times.8 blocks: four luminance (Y) blocks, one chrominance red (Cr) block and one chrominance blue (Cb) block. The luminance blocks correspond to sets of 8.times.8 pixels on a display and control the brightness of respective pixels. The chrominance blocks to a large extent control the colors for sets of four pixels. For each set of four pixels on the display, there is a single Cr characteristic and a single Cb characteristic.
For example, referring to FIG. 1, labeled prior art, a picture presented by a typical display includes 240 lines of video information in which each line has 352 pixels. Accordingly, a picture includes 240.times.352=84,480 pixel locations. Under the MPEG standard, this picture of video includes 44 by 30 luminance blocks or 1320 blocks of luminance video information. Additionally, because each macroblock of information also includes two corresponding chrominance blocks, each picture of video information also includes 330 Cr blocks and 330 Cb blocks. Accordingly, each picture of video information requires 126,720 pixels or a total of 1,013,760 bits of bit mapped storage space for presentation on a display.
There are three types of pictures of video information which are defined by the MPEG standard, intra-pictures (I picture), forward predicted pictures (P picture) and bi-predicted pictures (B picture).
An I picture is encoded as a single image having no reference to any past or future picture. Each block of an I picture is encoded independently. Accordingly, when decoding an I picture, no motion processing is necessary. However, for the reasons discussed below, it is necessary to store and access I pictures for use in decoding other types of pictures.
A P picture is encoded relative to a past reference picture. A reference picture is a P or I picture. The past reference picture is the closest preceding reference picture. Each macroblock in a P picture can be encoded either as an I macroblock or as a P macroblock. A P macroblock is stored as a translated 16.times.16 area of a past reference picture plus an error term. To specify the location of the P macroblock, a motion vector (i.e., an indication of the relative position of the macroblock in the current picture to the position of the translated area in the past reference picture) is also encoded. When decoding a P macroblock, the 16.times.16 area from the reference picture is offset according to a motion vector. The decoding function accordingly includes motion compensation, which is performed on a macroblock, in combination with error (IDCT) terms, which are defined on a block by block basis.
A B picture is encoded relative to the past reference picture and a future reference picture. The future reference picture is the closest proceeding reference picture. Accordingly, the decoding of a B picture is similar to that of an P picture with the exception that a B picture motion vector may refer to areas in the future of the reference picture. For macroblocks that use both past and future reference pictures, the two 16.times.16 areas are averaged. The macroblocks from the reference pictures are offset according to motion vectors.
Pictures are coded using a discrete cosine transform (DCT) coding scheme which transforms pixels (or error terms) into a set of coefficients corresponding to amplitudes of specific cosine basis functions. The discrete cosine transform is applied in image compression to decorrelate picture data prior to quantization. The DCT coefficients are further coded using variable length coding. Variable length coding (VLC) is a statistical coding technique that assigns codewords to values to be encoded. Values of high frequency of occurrence are assigned short codewords, and those of infrequent occurrence are assigned long codewords. On the average, the more frequent shorter codewords dominate so that the code string is shorter than the original data.
For a video system to provide a motion video capability, compressed video information must be quickly and efficiently decoded. One aspect of the decoding process is inverse discrete cosine transformation (IDCT). A second aspect is a motion compensation operation. Both the IDCT operation and the motion compensation operation are computationally intensive operations. Over a wide range of processor capabilities and image characteristics, a condition sometimes arises in which the picture decoding operation overburdens a video system. Under this condition, video frames are commonly dropped or a lag in motion video results. A technique for providing such highly efficient inverse discrete transformation and decoding is necessary.
Pictures are coded and restored using the MPEG standard employing a prediction operation in which values of pixels within a picture are predicted from a previously occurring picture or, in some circumstances, a later occurring picture. Prediction typically utilizes a motion compensation operation in which values of pixels within a picture are predicted to be the same as the previous picture except that the position of the pixels is shifted by a motion vector. Differences between an actual picture and its corresponding predicted picture are then determined and encoded by transforming the difference data using a discrete cosine transform (DCT) operation, quantizing the difference terms and by variable-length coding the DCT coefficients. In this manner, a predicted picture is stored or communicated in the form of a video bitstream of the motion vectors and DCT coefficient blocks. When a video stream of coded values is restored, a predicted picture is obtained by shifting the pixels in the picture previous to the predicted picture in accordance with the motion vector, inverse quantizing and inverse discrete cosine transforming the stored difference term DCT coefficients and adding the restored error terms to the restored motion compensated pixels. Because of the quantization of data, the resulting restored pixel values are typically not the same as the original pixel values. Generally, the differences in restored pixel values are not noticeable. However, at the high and low boundaries of the pixel value range, the differences can result in overflow and underflow of the defined pixel range. Overflow causes very white pixels to appear in a generally black background. Underflow results in very dark pixels in a generally white background. Pixel values that result from underflow and overflow produce what is called "speckle" in a picture.
Typical MPEG standard video systems eliminate speckle using a saturation arithmetic operation, called a "saturation-add" instruction or operation, which adds an error value to a pixel value, detects overflow and underflow of summed pixel values, and sets the pixel values of overflowed and underflowed pixels to near the maximum and minimum possible pixel values, respectively. The saturation-add operation for 8-bit pixel values is described by pseudocode as follows: EQU pixel.sub.i +error.sub.i =result.sub.i EQU if (result.sub.i &lt;0) result.sub.i =0; EQU if (result.sub.i &gt;255) result.sub.i =255;
where pixel.sub.i refers to a pixel value restored from motion compensation, error.sub.i refers to an inverse quantized and inverse discrete cosine transformed error term and result.sub.i refers to the sum of the pixel and error terms. In this example, result.sub.i is an eight-bit variable so that a valid range of pixel values is 0-255.
The saturation-add operation is typically performed by a hard-coded subroutine or using a lookup table. In either case, the saturation operation is costly in terms of computational burden and, therefore, speed of operation. What is needed is a saturation-add operation that greatly reduces computational burden but which substantially retains video quality.